// https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/

class Solution
{
public:
  int findLength(vector<int> &A, vector<int> &B)
  {
    // 两个数组各自的长度
    int n = A.size(), m = B.size();

    // dp[n+1][m+1] = 0 下标都统一从【1】开始
    //
    // dp[i][j] 含义：
    //  - 表示 A[i:] 和 B[j:] 最长公共前缀
    //  - A[i:] 表示 数组 A 中的 [i, n] 子数组
    //  - B[j:] 表示 数组 B 中的 [j, m] 子数组
    //
    // dp[i][j] = 0 默认值，表示 A[i:] 与 B[:j] 最长重复子数组 长度为 0
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    //【最大的】 A[i:] 和 B[j:] 最长重复子数组【长度】
    int max_len = 0;

    // 从【后】往【前】统计 A[i,n] 与 B[j,m] 最大相同子序列的总个数
    // - A[i] == B[j], dp[i][j] = dp[i + 1][j + 1] + 1
    // - A[i] != B[j], dp[i][j] = 0
    for (int i = n - 1; i >= 0; i--)
    {
      for (int j = m - 1; j >= 0; j--)
      {
        // 如果 A[i] 与 B[j] 相等，那么 dp[i][j] = dp[i + 1][j + 1] 的值 + 1 ===> 最长相同子序列个数 + 1
        // dp[i][j] = A[i] == B[j] ? (dp[i + 1][j + 1] + 1) : 0;
        if (A[i] == B[j])
        {
          dp[i][j] = dp[i + 1][j + 1] + 1; // 重复子数组 总长度 + 1
        }
        else
        {
          dp[i][j] = 0; // 没有重复的子数组元素
        }

        // 更新【最大】最长相同子序列个数
        max_len = max(max_len, dp[i][j]);
      }
    }

    return max_len;
  }
};
